Wakeup scheduling has been widely used in wireless sensor networks (WSNs), for it can reduce the energy wastage caused by the\r\nidle listening state. In a traditional wakeup scheduling, sensor nodes start up numerous times in a period, thus consuming extra\r\nenergy due to state transitions (e.g., from the sleep state to the active state). In this paper, we address a novel interference-free\r\nwakeup scheduling problem called compact wakeup scheduling, in which a node needs to wake up only once to communicate\r\nbidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and it\r\nis NP-complete to decide whether a valid compact wakeup scheduling exists for an arbitrary graph. In particular, tree and grid\r\ntopologies, which are commonly used inWSNs, have valid compact wakeup schedulings.We propose polynomial-time algorithms\r\nusing the optimum number of time slots in a period for trees and grid graphs. Simulations further validate our theoretical results.
Loading....